package com.wushijia.datastructure.tree;

public class BinarySortTree<E> {

  protected BinaryNode<E> root;

  public BinarySortTree() {
    root = null;
  }

  public boolean isEmpty() {
    return this.root == null;
  }

  public void inOrder() {
    System.out.print("\n inorder is:");
      if (root != null) {
          inOrder(root);
      }
    System.out.println();
  }

  private void inOrder(BinaryNode<E> p) {
    if (p != null) {
      inOrder(p.left);
      System.out.print(p.data + " ");
      inOrder(p.right);
    }
  }

  public BinaryNode<E> search(E value) {
      if (value == null || !(value instanceof Comparable)) {
          return null;
      }
    Comparable cmpobj = (Comparable) value;
    BinaryNode<E> p = this.root;
    while (p != null && cmpobj.compareTo(p.data) != 0) {
      System.out.print(p.data + "? ");
        if (cmpobj.compareTo(p.data) < 0) {
            p = p.left;
        } else {
            p = p.right;
        }
    }
    return p;
  }

  public boolean insert(E value) {
      if (value == null || !(value instanceof Comparable)) {
          return false;
      }
    if (root == null) {
      root = new BinaryNode<E>(value);
      return true;
    }
    return insert(value, root);
  }

  private boolean insert(E value, BinaryNode<E> p) {
    Comparable cmpobj = (Comparable) value;
      if (cmpobj.compareTo(p.data) == 0) {
          return false;
      }

      if (cmpobj.compareTo(p.data) < 0) {
          if (p.left == null) {
              p.left = new BinaryNode<E>(value);
              return true;
          } else {
              return insert(value, p.left);
          }
      } else if (p.right == null) {
          p.right = new BinaryNode<E>(value);
          return true;
      } else {
          return insert(value, p.right);
      }
  }

  public E remove(E value) {
      if (root == null || value == null || !(value instanceof Comparable)) {
          return null;
      }
    return remove(value, root, null);
  }

  private E remove(E value, BinaryNode<E> p, BinaryNode<E> parent) {
    Comparable cmpobj = (Comparable) value;
    if (p != null) {
        if (cmpobj.compareTo(p.data) < 0) {
            return remove(value, p.left, p);
        } else if (cmpobj.compareTo(p.data) > 0) {
            return remove(value, p.right, p);
        } else if (p.left != null && p.right != null) {
            BinaryNode<E> innext = p.right;
            while (innext.left != null) {
                innext = innext.left;
            }
            p.data = innext.data;
            return remove(p.data, p.right, p);
        } else {
            if (parent == null) {
                if (p.left != null) {
                    root = p.left;
                } else {
                    root = p.right;
                }
                return p.data;
            }

            if (p == parent.left) {
                if (p.left != null) {
                    parent.left = p.left;
                } else {
                    parent.left = p.right;
                }
            } else if (p.left != null) {
                parent.right = p.left;
            } else {
                parent.right = p.right;
            }
            return p.data;
        }
    }
    return null;
  }

  public static void main(String args[]) {
    BinarySortTree<Integer> bstree = new BinarySortTree<Integer>();
    System.out.print("insert: ");
    int[] key = {54, 18, 66, 87, 36, 12, 54, 81, 15, 76, 57, 6, 40, 99, 85};
      for (int i = 0; i < key.length; i++) {
          if (bstree.insert(new Integer(key[i]))) {
              System.out.print(key[i] + " ");
          }
      }
    bstree.inOrder();

    Integer element = new Integer(key[key.length - 1]);
    System.out.println("\n" + element + ", " + (bstree.search(element) != null ? " is " : " isn't ") + " find!");
    element = new Integer(50);
    System.out.println("\n" + element + ", " + (bstree.search(element) != null ? " is " : " isn't ") + " find!");

    Integer value = new Integer(66);
    System.out.print("remove:" + value + ", " + (bstree.remove(value) != null ? " can " : " can't ") + "remove!");
    bstree.inOrder();
    value = new Integer(67);
    System.out.print("remove:" + value + ", " + (bstree.remove(value) != null ? " can " : " can't ") + "remove!");
    bstree.inOrder();
  }
}